package EjercicioPilasColas;

import TDACola.EmptyQueueException;
import TDACola.LinkedQueue;
import TDACola.Queue;
import TDAPila.ArrayStack;
import TDAPila.EmptyStackException;
import TDAPila.Stack;

/**
 * Clase que encapsula un método para resolver el siguiente ejercicio:</br>
 * Dado el conjunto de símbolos <i>{a,b}</i>, llamaremos <i>{a,b}*</i> al conjunto de todas las cadenas constituidas por 0 o más símbolos de <i>{a,b}</i>.</br>
 * Por ejemplo, las cadenas <i>aaab</i>, <i>b</i>, <i>a</i>, <i>bababb</i> y <i>bbbb</i> pertenecen a <i>{a,b}*</i>.</br> 
 * Escriba un programa que tome como entrada una cadena de caracteres y determine si es de la forma: <b> A1 x A1'x A2 x A2' x ... x An x An' </b> donde:
 * <ul>
 * <li> el metasímbolo <i>Ai</i> representa una cadena de la forma <i>CzCC</i>, con <i>C</i> perteneciente a <i>{a,b}*</i>, es decir, si <i>C=abb</i> entonces, <i>CzCC = abbzabbabb</i>. </li>
 * <li> el metasímbolo <i>Ai'</i> representa la cadena <i>Ai</i> invertida, es decir si <i>A1=bzbb</i> entonces <i>A1'=bbzb</i>.
 * </ul> </br>
 * Los símbolos <b>x</b> y <b>z</b> son parte del lenguaje y son considerados como separadores.</br>
 * Ejemplos de cadenas válidas: </br>
 * <ul>
 * <li>bzbbxbbzb </li>
 * <li>azaaxaaza </li>
 * <li>abzababxbabazba </li>
 * <li>bzbbxbbzbxazaaxaaza </li>
 * <li>aaabzaaabaaabxbaaabaaazbaaaxabzababxbabazba</li>
 * </ul> </br>
 * 
 * <b>Requiere:</b> <i>TDAPila</i>, <i>TDACola</i>.
 * @author FJoaquin (federico.joaquin@cs.uns.edu.ar)
 */
public class EjercicioPilasColas {
	/**
	 * Determina si una cadena de caracteres cumple con el formato enunciado.
	 * @param cadena de caracteres a chequear si valida el formato enunciado.
	 * @return Verdadero si cadena respesta el formato enunciado; false en caso contrario.
	 */
	public static boolean chequear_cadena(String cadena){
		char c, c_en_cola, c_en_pila;
		boolean cumple, finalizo_c;
		
		int indice = 0;
		Stack<Character> pila = new ArrayStack<Character>();
		Queue<Character> cola_1 = new LinkedQueue<Character>();
		Queue<Character> cola_2 = new LinkedQueue<Character>();
		
		//Valida que la cadena no sea vacía, en tal caso, no cumple formato.
		cumple = !cadena.isEmpty();
		
		// Se valida Ai x Ai'.
		// Para esto:
		// -- Primero se tienen en cuenta los caracteres C en el formato.
		// -- Luego se valida que la cadena contenga los caracteres CC.
		// -- Por último, se valida que la cadena contenga CCzC.
		// En cualquier caso, cuando las restricciones no se cumplen, finaliza el cómputo indicando que el formato no es válido.
		while(cumple && indice < cadena.length()){
			//Se consideran los caracteres de la cadena que corresponde a C en el formato, esto es, hasta consumir el separador z.
			finalizo_c = false;
			while(cumple && !finalizo_c){
				//Si existen elementos a consumir en la cadena, se validan como parte de C. Se agregan todas las componentes de C en la pila y colas.
				//Caso contrario, la cadena no es válida para el formato enunciado.
				if (cadena.length() > indice){
					c = cadena.charAt(indice++);
					pila.push(c);
					//Si c es separador z, se debe validar CC en la cadena restante.
					//Caso contrario se valida que c sea caracter válido para C.
					if (c == 'z')						
						finalizo_c = true;
					else
						//Si se consume un caracter válido para C, se agregan en las ED auxiliares, y se prosigue en el estado validando C con la cadena restante.
						//Caso constrario la cadena no es válida para el formato enunciado.
						if (c == 'a' || c == 'b'){
							cola_1.enqueue(c);
							cola_2.enqueue(c);
						}else
							cumple = false;
				}else
					cumple = false;
			}
			
			//Valida que la cadena cumpla con el formato CC, considerando la primera componente C.
			while(cumple && indice<cadena.length() && !cola_1.isEmpty()){
				try { 
					c = cadena.charAt(indice++);
					c_en_cola = cola_1.dequeue(); 
					cumple = (c == c_en_cola);
					pila.push(c);
				} catch (EmptyQueueException e) {
					cumple = false;
				}
			}
			
			//Se asegura que la primera componente C haya sido validada, comprobando que cola_1 se haya vaciado.
			cumple = cumple && cola_1.isEmpty();
			
			//Valida que la cadena cumpla con el formato CC, considerando la segunda componente C.
			while(cumple && indice<cadena.length() && !cola_2.isEmpty()){
				try { 
					c = cadena.charAt(indice++);
					c_en_cola = cola_2.dequeue(); 
					cumple = (c == c_en_cola);
					pila.push(c);
				} catch (EmptyQueueException e) {
					cumple = false;
				}
			}
			
			//Se asegura que la segunda componente C haya sido validada, comprobando que cola_2 se haya vaciado.
			//Se asegura que la cadena aún tiene caracteres para validar x Ai'
			cumple = cumple && cola_2.isEmpty() && indice < cadena.length();
			
			//Valida que en la cadena el próximo caracter sea el separador x
			if (cumple){
				c = cadena.charAt(indice++);
				cumple = (c == 'x');
			}
			
			//Valida que la cadena restante cumpla con el formato Ai'
			while(cumple && indice < cadena.length() && !pila.isEmpty()){
				try{
					c = cadena.charAt(indice++);
					c_en_pila = pila.pop();
					cumple = (c == c_en_pila);
				}catch(EmptyStackException e){
					cumple = false;
				}
			}
			
			//Se asegura que la componente Ai' haya sido validad, comprobando que la pila se haya vaciado.
			cumple = cumple && pila.isEmpty();
			
			//Si la cadena aún contiene caracteres, se asegura que el próximo caracter sea un separador x, que haya más caracteres luego de el separador
			//y se prosigue validando el próximo Ai x Ai'
			if (indice < cadena.length())
				cumple = cumple && (cadena.charAt(indice++) == 'x' && indice < cadena.length());
		}
		
		return cumple;
	}
	
	/**
	 * Método que inicia la ejecución del programa.
	 * Testea el funcionamiento de <i>chequear_cadena</i> con algunas cadenas de prueba.
	 * @param args Argumentos por línea de comandos.
	 */
	public static void main(String [] args){
		String cadena;
		
		System.out.println("Casos de prueba sobre cadenas válidas (cadenas ejemplo de enunciado)");
		
		cadena = "bzbbxbbzb";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "azaaxaaza";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "abzababxbabazba";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "bzbbxbbzbxazaaxaaza";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "aaabzaaabaaabxbaaabaaazbaaaxabzababxbabazba";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		System.out.println("\nCasos de prueba sobre cadenas válidas (ejemplos agregados)");
		
		cadena = "zxz";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "zxzxzxzxzxz";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
			
		System.out.println("\nCasos de prueba sobre cadenas no válidas (ejemplos agregados)");
					
		cadena = "";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "zz";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "zx";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "x";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "fzffxffzf";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "bzbbxbbzbx";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "bzzbbxbbzb";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "bzbbxbbzzb";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "bbbxbbzbx";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
		
		cadena = "bzbbbbzbx";
		System.out.println("Chequear_cadena(\"" + cadena + "\") = " + chequear_cadena(cadena));
	}
}
